#include<vector>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;

class Solution {
private:
    bool reduce(const string& S,int index, unsigned long long first, unsigned long long second,vector<int>&res) {
        if (index == S.length())
            return true;
        unsigned long long tmp = 0;
        bool flag = S[index] == '0';
        while (index < S.length()) {
            tmp = tmp * 10 + S[index] - '0';
            if (tmp > INT32_MAX)
                break;
            if (tmp == first + second) {
                res.push_back(tmp);
                if (reduce(S, index+1, second, tmp, res))
                    return true;
                res.pop_back();
            }
            if (flag)
                break;
            ++index;
        }
        return false;
    }

public:
    vector<int> splitIntoFibonacci(string S) {
        unsigned long long first = 0, second = 0;
        vector<int>res;
        for (int i = 0; i < S.length(); ++i) {
            first = first * 10 + S[i] - '0';
            if (first > INT32_MAX) break;
            second = 0;
            res.push_back(first);
            for (int j = i + 1; (static_cast<int>(S.length())-j-1) >= max(i+1,j-i); ++j) {
                second = second * 10 + S[j] - '0';
                if (second > INT32_MAX)
                    break;
                res.push_back(second);
                if (reduce(S, j + 1, first, second, res))
                    return res;
                res.pop_back();
                if (S[i + 1] == '0')
                    break;
            }
            res.pop_back();
            if (S[0] == '0')
                break;
        }
        return res;
    }
};

//int main() {
//    Solution sol;
//    sol.splitIntoFibonacci("112358130");
//}